package com.it.zhangjun.arithmetic.栈;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author zhangj
 * @description 找出数组中右边比我小的元素
 * @date 2021-03-18 20:28
 */
public class LT_找出数组中右边比我小的元素 {
    public static void main(String[] args) {
        int[] A = {1, 2, 4, 9, 4, 0, 5};
        int[] rightSmall = findRightSmall(A);
        Arrays.stream(rightSmall).forEach(System.out::print);
    }

    private static int[] findRightSmall(int[] A) {
        // 结果数组
        int[] ans = new int[A.length];
        //栈中的元素记录的是下标
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < A.length; i++) {
            int x = A[i];
            while (!stack.isEmpty() && A[stack.peek()] > x) {
                //消除的时候，记录下被谁消除的
                ans[stack.peek()] = i;
                //值大的需要从栈中弹出
                stack.pop();
            }
            //剩下的入栈
            stack.push(i);
        }
        //栈中剩下的元素，由于没有人来消除他们，因此，将其设置为-1
        while (!stack.isEmpty()) {
            ans[stack.peek()] = -1;
            stack.pop();
        }
        return ans;
    }
}